package chapter7.graph;

/**
 * Created by lili on 2017/7/1.
 */
//【例7.5】  以Floyd算法求带权图每对顶点间的最短路径。
//
public class WeightedDirectedG12                  //带权有向图G12
{
    public static void main(String args[])
    {
        String[] vertices={"A","B","C","D","E","F"};
        Edge edges[]={new Edge(0,1,24), new Edge(0,4,76),
                new Edge(1,2,32),
                new Edge(2,5,39),
                new Edge(3,2,13), new Edge(3,4,21),
                new Edge(4,5,27),
                new Edge(5,0,16), new Edge(5,1,41), new Edge(5,3,30)};
        AdjMatrixGraph<String> graph = new AdjMatrixGraph<String>(vertices, edges);
        System.out.print("带权有向图G12，"+graph.toString());
//        for (int i=0; i<graph.vertexCount(); i++)
//            graph.shortestPath(i);               //顶点vi的单源最短路径，Dijkstra算法
        graph.shortestPath();                    //调用Floyd算法求带权图每对顶点间的最短路径
    }
}
/*
程序运行结果如下：
//Dijkstra算法

  //Floyd算法
带权有向图G12，顶点集合：(A, B, C, D, E, F)
邻接矩阵:
  0  24  ∞  ∞  76  ∞
  ∞  0  32  ∞  ∞  ∞
  ∞  ∞  0  ∞  ∞  39
  ∞  ∞  13  0  21  ∞
  ∞  ∞  ∞  ∞  0  27
  16  41  ∞  30  ∞  0
初值path数组
  -1  0  -1  -1  0  -1
  -1  -1  1  -1  -1  -1
  -1  -1  -1  -1  -1  2
  -1  -1  3  -1  3  -1
  -1  -1  -1  -1  -1  4
  5  5  -1  5  -1  -1
dist数组
  0  24  ∞  ∞  76  ∞
  ∞  0  32  ∞  ∞  ∞
  ∞  ∞  0  ∞  ∞  39
  ∞  ∞  13  0  21  ∞
  ∞  ∞  ∞  ∞  0  27
  16  41  ∞  30  ∞  0

以A作为中间顶点
(B,C)路径长度32，替换为(B,A),(A,C)路径长度199998？否
(B,D)路径长度99999，替换为(B,A),(A,D)路径长度199998？否
(B,E)路径长度99999，替换为(B,A),(A,E)路径长度100075？否
(B,F)路径长度99999，替换为(B,A),(A,F)路径长度199998？否
(C,B)路径长度99999，替换为(C,A),(A,B)路径长度100023？否
(C,D)路径长度99999，替换为(C,A),(A,D)路径长度199998？否
(C,E)路径长度99999，替换为(C,A),(A,E)路径长度100075？否
(C,F)路径长度39，替换为(C,A),(A,F)路径长度199998？否
(D,B)路径长度99999，替换为(D,A),(A,B)路径长度100023？否
(D,C)路径长度13，替换为(D,A),(A,C)路径长度199998？否
(D,E)路径长度21，替换为(D,A),(A,E)路径长度100075？否
(D,F)路径长度99999，替换为(D,A),(A,F)路径长度199998？否
(E,B)路径长度99999，替换为(E,A),(A,B)路径长度100023？否
(E,C)路径长度99999，替换为(E,A),(A,C)路径长度199998？否
(E,D)路径长度99999，替换为(E,A),(A,D)路径长度199998？否
(E,F)路径长度27，替换为(E,A),(A,F)路径长度199998？否
(F,B)路径长度41，替换为(F,A),(A,B)路径长度40？是，d51=40，p51=0
(F,C)路径长度99999，替换为(F,A),(A,C)路径长度100015？否
(F,D)路径长度30，替换为(F,A),(A,D)路径长度100015？否
(F,E)路径长度99999，替换为(F,A),(A,E)路径长度92？是，d54=92，p54=0
path数组
  -1  0  -1  -1  0  -1
  -1  -1  1  -1  -1  -1
  -1  -1  -1  -1  -1  2
  -1  -1  3  -1  3  -1
  -1  -1  -1  -1  -1  4
  5  0  -1  5  0  -1
dist数组
  0  24  ∞  ∞  76  ∞
  ∞  0  32  ∞  ∞  ∞
  ∞  ∞  0  ∞  ∞  39
  ∞  ∞  13  0  21  ∞
  ∞  ∞  ∞  ∞  0  27
  16  40  ∞  30  92  0

以B作为中间顶点
(A,C)路径长度99999，替换为(A,B),(B,C)路径长度56？是，d02=56，p02=1
(A,D)路径长度99999，替换为(A,B),(B,D)路径长度100023？否
(A,E)路径长度76，替换为(A,B),(B,E)路径长度100023？否
(A,F)路径长度99999，替换为(A,B),(B,F)路径长度100023？否
(C,A)路径长度99999，替换为(C,B),(B,A)路径长度199998？否
(C,D)路径长度99999，替换为(C,B),(B,D)路径长度199998？否
(C,E)路径长度99999，替换为(C,B),(B,E)路径长度199998？否
(C,F)路径长度39，替换为(C,B),(B,F)路径长度199998？否
(D,A)路径长度99999，替换为(D,B),(B,A)路径长度199998？否
(D,C)路径长度13，替换为(D,B),(B,C)路径长度100031？否
(D,E)路径长度21，替换为(D,B),(B,E)路径长度199998？否
(D,F)路径长度99999，替换为(D,B),(B,F)路径长度199998？否
(E,A)路径长度99999，替换为(E,B),(B,A)路径长度199998？否
(E,C)路径长度99999，替换为(E,B),(B,C)路径长度100031？否
(E,D)路径长度99999，替换为(E,B),(B,D)路径长度199998？否
(E,F)路径长度27，替换为(E,B),(B,F)路径长度199998？否
(F,A)路径长度16，替换为(F,A,B),(B,A)路径长度100039？否
(F,C)路径长度99999，替换为(F,A,B),(B,C)路径长度72？是，d52=72，p52=1
(F,D)路径长度30，替换为(F,A,B),(B,D)路径长度100039？否
(F,A,E)路径长度92，替换为(F,A,B),(B,E)路径长度100039？否
path数组
  -1  0  1  -1  0  -1
  -1  -1  1  -1  -1  -1
  -1  -1  -1  -1  -1  2
  -1  -1  3  -1  3  -1
  -1  -1  -1  -1  -1  4
  5  0  1  5  0  -1
dist数组
  0  24  56  ∞  76  ∞
  ∞  0  32  ∞  ∞  ∞
  ∞  ∞  0  ∞  ∞  39
  ∞  ∞  13  0  21  ∞
  ∞  ∞  ∞  ∞  0  27
  16  40  72  30  92  0

以C作为中间顶点
(A,B)路径长度24，替换为(A,B,C),(C,B)路径长度100055？否
(A,D)路径长度99999，替换为(A,B,C),(C,D)路径长度100055？否
(A,E)路径长度76，替换为(A,B,C),(C,E)路径长度100055？否
(A,F)路径长度99999，替换为(A,B,C),(C,F)路径长度95？是，d05=95，p05=2
(B,A)路径长度99999，替换为(B,C),(C,A)路径长度100031？否
(B,D)路径长度99999，替换为(B,C),(C,D)路径长度100031？否
(B,E)路径长度99999，替换为(B,C),(C,E)路径长度100031？否
(B,F)路径长度99999，替换为(B,C),(C,F)路径长度71？是，d15=71，p15=2
(D,A)路径长度99999，替换为(D,C),(C,A)路径长度100012？否
(D,B)路径长度99999，替换为(D,C),(C,B)路径长度100012？否
(D,E)路径长度21，替换为(D,C),(C,E)路径长度100012？否
(D,F)路径长度99999，替换为(D,C),(C,F)路径长度52？是，d35=52，p35=2
(E,A)路径长度99999，替换为(E,C),(C,A)路径长度199998？否
(E,B)路径长度99999，替换为(E,C),(C,B)路径长度199998？否
(E,D)路径长度99999，替换为(E,C),(C,D)路径长度199998？否
(E,F)路径长度27，替换为(E,C),(C,F)路径长度100038？否
(F,A)路径长度16，替换为(F,A,B,C),(C,A)路径长度100071？否
(F,A,B)路径长度40，替换为(F,A,B,C),(C,B)路径长度100071？否
(F,D)路径长度30，替换为(F,A,B,C),(C,D)路径长度100071？否
(F,A,E)路径长度92，替换为(F,A,B,C),(C,E)路径长度100071？否
path数组
  -1  0  1  -1  0  2
  -1  -1  1  -1  -1  2
  -1  -1  -1  -1  -1  2
  -1  -1  3  -1  3  2
  -1  -1  -1  -1  -1  4
  5  0  1  5  0  -1
dist数组
  0  24  56  ∞  76  95
  ∞  0  32  ∞  ∞  71
  ∞  ∞  0  ∞  ∞  39
  ∞  ∞  13  0  21  52
  ∞  ∞  ∞  ∞  0  27
  16  40  72  30  92  0

以D作为中间顶点
(A,B)路径长度24，替换为(A,D),(D,B)路径长度199998？否
(A,B,C)路径长度56，替换为(A,D),(D,C)路径长度100012？否
(A,E)路径长度76，替换为(A,D),(D,E)路径长度100020？否
(A,B,C,F)路径长度95，替换为(A,D),(D,C,F)路径长度100051？否
(B,A)路径长度99999，替换为(B,D),(D,A)路径长度199998？否
(B,C)路径长度32，替换为(B,D),(D,C)路径长度100012？否
(B,E)路径长度99999，替换为(B,D),(D,E)路径长度100020？否
(B,C,F)路径长度71，替换为(B,D),(D,C,F)路径长度100051？否
(C,A)路径长度99999，替换为(C,D),(D,A)路径长度199998？否
(C,B)路径长度99999，替换为(C,D),(D,B)路径长度199998？否
(C,E)路径长度99999，替换为(C,D),(D,E)路径长度100020？否
(C,F)路径长度39，替换为(C,D),(D,C,F)路径长度100051？否
(E,A)路径长度99999，替换为(E,D),(D,A)路径长度199998？否
(E,B)路径长度99999，替换为(E,D),(D,B)路径长度199998？否
(E,C)路径长度99999，替换为(E,D),(D,C)路径长度100012？否
(E,F)路径长度27，替换为(E,D),(D,C,F)路径长度100051？否
(F,A)路径长度16，替换为(F,D),(D,A)路径长度100029？否
(F,A,B)路径长度40，替换为(F,D),(D,B)路径长度100029？否
(F,A,B,C)路径长度72，替换为(F,D),(D,C)路径长度43？是，d52=43，p52=3
(F,A,E)路径长度92，替换为(F,D),(D,E)路径长度51？是，d54=51，p54=3
path数组
  -1  0  1  -1  0  2
  -1  -1  1  -1  -1  2
  -1  -1  -1  -1  -1  2
  -1  -1  3  -1  3  2
  -1  -1  -1  -1  -1  4
  5  0  3  5  3  -1
dist数组
  0  24  56  ∞  76  95
  ∞  0  32  ∞  ∞  71
  ∞  ∞  0  ∞  ∞  39
  ∞  ∞  13  0  21  52
  ∞  ∞  ∞  ∞  0  27
  16  40  43  30  51  0

以E作为中间顶点
(A,B)路径长度24，替换为(A,E),(E,B)路径长度100075？否
(A,B,C)路径长度56，替换为(A,E),(E,C)路径长度100075？否
(A,D)路径长度99999，替换为(A,E),(E,D)路径长度100075？否
(A,B,C,F)路径长度95，替换为(A,E),(E,F)路径长度103？否
(B,A)路径长度99999，替换为(B,E),(E,A)路径长度199998？否
(B,C)路径长度32，替换为(B,E),(E,C)路径长度199998？否
(B,D)路径长度99999，替换为(B,E),(E,D)路径长度199998？否
(B,C,F)路径长度71，替换为(B,E),(E,F)路径长度100026？否
(C,A)路径长度99999，替换为(C,E),(E,A)路径长度199998？否
(C,B)路径长度99999，替换为(C,E),(E,B)路径长度199998？否
(C,D)路径长度99999，替换为(C,E),(E,D)路径长度199998？否
(C,F)路径长度39，替换为(C,E),(E,F)路径长度100026？否
(D,A)路径长度99999，替换为(D,E),(E,A)路径长度100020？否
(D,B)路径长度99999，替换为(D,E),(E,B)路径长度100020？否
(D,C)路径长度13，替换为(D,E),(E,C)路径长度100020？否
(D,C,F)路径长度52，替换为(D,E),(E,F)路径长度48？是，d35=48，p35=4
(F,A)路径长度16，替换为(F,D,E),(E,A)路径长度100050？否
(F,A,B)路径长度40，替换为(F,D,E),(E,B)路径长度100050？否
(F,D,C)路径长度43，替换为(F,D,E),(E,C)路径长度100050？否
(F,D)路径长度30，替换为(F,D,E),(E,D)路径长度100050？否
path数组
  -1  0  1  -1  0  2
  -1  -1  1  -1  -1  2
  -1  -1  -1  -1  -1  2
  -1  -1  3  -1  3  4
  -1  -1  -1  -1  -1  4
  5  0  3  5  3  -1
dist数组
  0  24  56  ∞  76  95
  ∞  0  32  ∞  ∞  71
  ∞  ∞  0  ∞  ∞  39
  ∞  ∞  13  0  21  48
  ∞  ∞  ∞  ∞  0  27
  16  40  43  30  51  0

以F作为中间顶点
(A,B)路径长度24，替换为(A,B,C,F),(F,A,B)路径长度135？否
(A,B,C)路径长度56，替换为(A,B,C,F),(F,D,C)路径长度138？否
(A,D)路径长度99999，替换为(A,B,C,F),(F,D)路径长度125？是，d03=125，p03=5
(A,E)路径长度76，替换为(A,B,C,F),(F,D,E)路径长度146？否
(B,A)路径长度99999，替换为(B,C,F),(F,A)路径长度87？是，d10=87，p10=5
(B,C)路径长度32，替换为(B,C,F),(F,D,C)路径长度114？否
(B,D)路径长度99999，替换为(B,C,F),(F,D)路径长度101？是，d13=101，p13=5
(B,E)路径长度99999，替换为(B,C,F),(F,D,E)路径长度122？是，d14=122，p14=3
(C,A)路径长度99999，替换为(C,F),(F,A)路径长度55？是，d20=55，p20=5
(C,B)路径长度99999，替换为(C,F),(F,A,B)路径长度79？是，d21=79，p21=0
(C,D)路径长度99999，替换为(C,F),(F,D)路径长度69？是，d23=69，p23=5
(C,E)路径长度99999，替换为(C,F),(F,D,E)路径长度90？是，d24=90，p24=3
(D,A)路径长度99999，替换为(D,E,F),(F,A)路径长度64？是，d30=64，p30=5
(D,B)路径长度99999，替换为(D,E,F),(F,A,B)路径长度88？是，d31=88，p31=0
(D,C)路径长度13，替换为(D,E,F),(F,D,C)路径长度91？否
(D,E)路径长度21，替换为(D,E,F),(F,D,E)路径长度99？否
(E,A)路径长度99999，替换为(E,F),(F,A)路径长度43？是，d40=43，p40=5
(E,B)路径长度99999，替换为(E,F),(F,A,B)路径长度67？是，d41=67，p41=0
(E,C)路径长度99999，替换为(E,F),(F,D,C)路径长度70？是，d42=70，p42=3
(E,D)路径长度99999，替换为(E,F),(F,D)路径长度57？是，d43=57，p43=5
path数组
  -1  0  1  5  0  2
  5  -1  1  5  3  2
  5  0  -1  5  3  2
  5  0  3  -1  3  4
  5  0  3  5  -1  4
  5  0  3  5  3  -1
dist数组
  0  24  56  125  76  95
  87  0  32  101  122  71
  55  79  0  69  90  39
  64  88  13  0  21  48
  43  67  70  57  0  27
  16  40  43  30  51  0

每对顶点间的最短路径如下：
(A,B)长度为24
(A,B,C)长度为56
(A,B,C,F,D)长度为125
(A,E)长度为76
(A,B,C,F)长度为95
(B,C,F,A)长度为87
(B,C)长度为32
(B,C,F,D)长度为101
(B,C,F,D,E)长度为122
(B,C,F)长度为71
(C,F,A)长度为55
(C,F,A,B)长度为79
(C,F,D)长度为69
(C,F,D,E)长度为90
(C,F)长度为39
(D,E,F,A)长度为64
(D,E,F,A,B)长度为88
(D,C)长度为13
(D,E)长度为21
(D,E,F)长度为48
(E,F,A)长度为43
(E,F,A,B)长度为67
(E,F,D,C)长度为70
(E,F,D)长度为57
(E,F)长度为27
(F,A)长度为16
(F,A,B)长度为40
(F,D,C)长度为43
(F,D)长度为30
(F,D,E)长度为51

*/


